Comparatif HsIndex

Date de publication : 20/10/2020

Lorsque j'ai commencé à développer sérieusement avec Haskell, je n'avais pas l'expérience que j'ai actuellement et j'ai pris certaines habitudes qui ne sont pas forcément les bonnes. Afin d’accroître encore mon niveau j'ai décidé de vérifier l'impact de ces choix sur mes programmes afin d'en tirer un enseignement pour la suite.

Lorsque j'ai commencé à programmer HsIndex il y a maintenant 3 ans, j'ai utilisé le type String pour manipuler les mots et créer les lignes de texte à inclure dans le fichier à inclure dans LaTeX. Pour manipuler du texte, la bibliothèque text incluse dans haskell-plateform permet théoriquement d'avoir de meilleurs performances tout en apportant des fonctions permettant de modifier du texte plus facilement qu'avec le type String¹.

Je souhaiterais également améliorer mon parser afin de rendre le programme plus rapide. Lorsque je l'ai écrit, je l'ai fait un peu à la va-vite sans trop réfléchir ni prendre le temps de l'optimiser.

Je souhaiterais donc voir quel est l'influence de ces optimisations et les gains en temps et en mémoire utilisée par rapport à la version de départ. J'en profiterais également pour voir quelle est l'influence des optimisations natives offertes par le compilateur ghc. De mémoire elles étaient d'environ 10 à 20% par rapport à une version non optimisée mais j'aimerais en avoir le cœur net.

Méthodologie

Versions du programme

Pour cela, il est nécessaire de compiler les différentes versions du programme d'après les sources avec les options adéquates. Pour l'étude détaillée des performances de chaque fonction, il est nécessaire d'utiliser une version du programme compilée avec une option spécifique pour faire du profiling (investigation). Ceci permettra d'obtenir pour chaque appel de fonction le temps qu'elle a mis pour s’exécuter et la mémoire qui lui a été allouée.

On utilisera également des versions compilées sans ces options de profiling pour effectuer des tests de vitesses.

On compile donc les versions profiling avec :

ghc -O0 hsindex.hs -prof -fprof-auto -fprof-cafs  -fforce-recomp

ghc -O2 hsindex.hs -prof -fprof-auto -fprof-cafs  -fforce-recomp

-O0 : 

Produit une version sans optimisation.

-O2 : 

Produit une version avec toutes les optimisations possibles.

-fforce-recomp : 

Force la recompilation de tous les fichiers sources du .programme

et les versions standard avec :

ghc -O0 hsindex.hs -fforce-recomp

ghc -O2 hsindex.hs -fforce-recomp

On aura donc 16 versions différentes du programme à analyser

0.9.1 : 

Version de référence.

0.9.1opti : 

Version avec le parser optimisé.

0.10.0 : 

Version avec le type Text.

0.11.0 : 

Version avec le parser optimisé et le type Text.

Matériel

Ce test sera réalisé sur une machine tournant sous Linux Debian 10 avec un processeur AMD FX-8350 8 cœurs (FD8350FRW8KHK) avec 32Go de mémoire DDR3

Fichiers de test

Pour évaluer les performances du programme, je vais utiliser 4 fichiers d'index idx différents. Deux seront issus de LaTeX (l'original) et deux autres de XeLaTeX sa version améliorée. Pour chacun, je prendrais un fichier français et russe (avec les caractères non ascii)

Les différents fichiers sont:

• Générés avec LaTeX :

  • Fichier français :

  • Fichier Russe :

• Générés avec XeLaTeX :

  • Fichier français :

  • Fichier Russe :

Ces fichiers ont le même nombre de ligne (2200). Un nombre plus important aurait été préférable mais le nombre de mot russes étant limitant, il n'a pas été possible d'avoir des fichiers plus gros.

Commandes

Les programmes seront lancés en batch avec BASH avec les commandes suivantes:

• Les versions normales seront lancées avec les commandes time pour obtenir le temps d’exécution:

  { time ./hsindex.0.9.1-O2  french --style="essai1.sty" -i indexes/motsfr.latex.idx -o motsfr.0.9.1-O2.latex.ind ; }  2>> timefr.latex.log 
  { time ./hsindex.0.9.1-O2  russian --style="essai1.sty" -i indexes/motsru.latex.idx -o motsru.0.9.1-O2.latex.ind ; }  2>> timeru.latex.log 
  

  Les accolades permettent de récupérer les sorties de la commande time et non de la commande hsindex.0.9.1-O0

• Les version de profiling seront lancées avec les commandes:

  ./hsindex.0.9.1-O2-prof  french --style="essai1.sty" -i indexes/motsfr.latex.idx -o motsfr.0.9.1-O2-prof.latex.ind  +RTS -p -pohsindex.0.9.1-O2-prof-fr-latex
  ./hsindex.0.9.1-O2-prof  russian --style="essai1.sty" -i indexes/motsru.latex.idx -o motsru.0.9.1-O2-prof.latex.ind  +RTS -p -pohsindex.0.9.1-O2-prof-ru-latex
  

  L'option +RTS est spécifique aux versions profiling et permet de passer des options dédiées à ce mode. -p et -po permettent d’extraire les résultats détaillés sous forme d'arborescence vers un fichier texte.

Test

Pour obtenir les temps d’exécution, on fait tourner chaque version du programme avec les 4 fichiers de tests en prenant soit de sauver les résultats dans des logs.

Les tests seront effectués :

• Sur la même machine.

• En mode uni-processeur.

• Sans autres tâche en cours d’exécution sur ma machine.

Résultats

Résultats version profiling

Les résultats synthétisés sous forme de tableaux sont:

	0.9.1-O0-prof	0.9.1-O2-prof	0.9.1opti-O0-prof	0.9.1opti-O2-prof	0.10.0-O0-prof	0.10.0-O2-prof	0.11.0-O0-prof	0.11.0-O2-prof
parseIeC	2,818	2,338	#N/D	#N/D	3,253	2,555	#N/D	#N/D
lstParseIeC.\	0,195	0,160	0,016	0,010	0,197	0,166	0,015	0,009
lstParseIeC	#N/D	#N/D	0,042	0,037	#N/D	#N/D	0,046	0,033
concatPagesItems.(…)	0,227	0,222	0,270	0,204	0,201	0,294	0,232	0,314
concatPagesItems.(…).\	0,227	0,065	0,249	0,077	0,120	#N/D	0,102	0,010
parseSymbol	0,127	0,089	#N/D	#N/D	0,098	0,118	#N/D	#N/D
braces	#N/D	#N/D	0,022	0,020	#N/D	#N/D	0,023	0,030
parseAnything	0,068	#N/D	0,049	0,034	0,073	#N/D	0,058	0,044
total time (secs)	3,980	3,080	0,840	0,480	4,280	3,380	0,670	0,530

	0.9.1-O0-prof	0.9.1-O2-prof	0.9.1opti-O0-prof	0.9.1opti-O2-prof	0.10.0-O0-prof	0.10.0-O2-prof	0.11.0-O0-prof	0.11.0-O2-prof
parseIeC	10,618	8,655	#N/D	#N/D	13,200	10,173	#N/D	#N/D
lstParseIeC.\	0,202	0,102	4,672	3,847	#N/D	#N/D	5,761	4,186
lstParseIeC	#N/D	#N/D	0,137	0,118	#N/D	#N/D	0,196	0,132
concatPagesItems.(…)	0,240	0,215	0,247	0,210	0,282	0,239	0,204	0,263
concatPagesItems.(…).\	0,190	#N/D	0,253	0,065	#N/D	#N/D	0,114	#N/D
parseSymbol	#N/D	#N/D	#N/D	#N/D	#N/D	#N/D	#N/D	#N/D
braces	1,188	1,054	1,363	1,049	1,673	1,266	1,705	1,304
parseAnything	#N/D	#N/D	#N/D	#N/D	#N/D	#N/D	#N/D	#N/D
total time (secs)	12,640	10,230	6,850	5,380	15,640	11,940	8,160	5,980

	0.9.1-O0-prof	0.9.1-O2-prof	0.9.1opti-O0-prof	0.9.1opti-O2-prof	0.10.0-O0-prof	0.10.0-O2-prof	0.11.0-O0-prof	0.11.0-O2-prof
parseIeC	2,852	2,353	#N/D	#N/D	3,227	2,614	#N/D	#N/D
lstParseIeC.\	0,224	0,135	#N/D	#N/D	0,199	0,182	#N/D	#N/D
lstParseIeC	#N/D	#N/D	0,039	0,028	#N/D	#N/D	0,039	0,025
concatPagesItems.(…)	0,322	0,196	0,248	0,221	0,203	0,268	0,217	0,293
concatPagesItems.(…).\	0,241	0,049	0,248	0,063	0,114	#N/D	0,105	0,025
parseSymbol	0,110	0,113	#N/D	#N/D	0,135	0,138	#N/D	#N/D
braces	#N/D	#N/D	0,020	0,021	#N/D	#N/D	0,019	0,024
parseAnything	0,057	0,046	0,052	0,050	0,063	#N/D	0,063	0,052
total time (secs)	4,080	3,060	0,790	0,470	4,230	3,440	0,620	0,490

	0.9.1-O0-prof	0.9.1-O2-prof	0.9.1opti-O0-prof	0.9.1opti-O2-prof	0.10.0-O0-prof	0.10.0-O2-prof	0.11.0-O0-prof	0.11.0-O2-prof
parseIeC	2,908	2,445	#N/D	#N/D	3,288	2,597	#N/D	#N/D
lstParseIeC.\	0,213	0,153	#N/D	#N/D	0,188	0,171	#N/D	#N/D
lstParseIeC	#N/D	#N/D	0,024	0,025	#N/D	#N/D	0,044	0,032
concatPagesItems.(…)	0,258	0,160	0,246	0,198	0,243	0,242	0,243	0,266
concatPagesItems.(…).\	0,254	0,063	0,222	0,072	0,094	#N/D	0,127	0,020
parseSymbol	0,115	0,100	#N/D	#N/D	0,128	0,111	#N/D	#N/D
braces	#N/D	#N/D	0,020	0,013	#N/D	#N/D	0,023	0,019
parseAnything	0,086	0,034	0,064	0,043	0,077	0,037	0,063	0,045
total time (secs)	4,090	3,130	0,740	0,440	4,270	3,360	0,660	0,450

Résultats version standard

	0.9.1-O0	0.9.1-O2	0.9.1opti-O0	0.9.1opti-O2	0.10.0-O0	0.10.0-O2	0.11.0-O0	0.11.0-O2
latex fr	2,806	2,005	0,772	0,53	2,783	2,232	0,735	0,541
latex ru	7,295	5,177	4,038	2,938	7,797	6,304	4,135	3,304
xetex fr	2,779	1,961	0,765	0,53	2,793	2,086	0,645	0,477
xetex ru	2,801	1,985	0,762	0,539	2,798	2,148	0,643	0,477

Comparatif des versions profiling

Gain de temps comparé à la version 0.9.1-O2

	0.9.1-O2-prof	0.9.1opti-O2-prof	0.10.0-O2-prof	0.11.0-O2-prof
latex fr	100,0%	-84,4%	9,7%	-82,8%
latex ru	100,0%	-47,4%	16,7%	-41,5%
xetex fr	100,0%	-84,6%	12,4%	-84,0%
xetex ru	100,0%	-85,9%	7,3%	-85,6%

Gain mémoire comparé à la version 0.9.1-O2

	0.9.1-O2-prof	0.9.1opti-O2-prof	0.10.0-O2-prof	0.11.0-O2-prof
latex fr	100,0%	-93,1%	11,6%	-92,6%
latex ru	100,0%	-45,9%	21,3%	-36,6%
xetex fr	100,0%	-93,7%	11,6%	-93,3%
xetex ru	100,0%	-93,8%	11,5%	-93,5%

Comparatif des versions normales

Gain de temps comparé aux version -O0

	0.9.1-O2	0.9.1opti-O2	0.10.0-O2	0.11.0-O2
latex fr	-28,5%	-31,3%	-19,8%	-26,4%
latex ru	-29,0%	-27,2%	-19,1%	-20,1%
xetex fr	-29,4%	-30,7%	-25,3%	-26,0%
xetex ru	-29,1%	-29,3%	-23,2%	-25,8%

Gain de temps comparé à la version 0.9.1-O2

	0.9.1-O2	0.9.1opti-O2	0.10.0-O2	0.11.0-O2
latex fr	100,0%	-73,6%	11,3%	-73,0%
latex ru	100,0%	-43,2%	21,8%	-36,2%
xetex fr	100,0%	-73,0%	6,4%	-75,7%
xetex ru	100,0%	-72,8%	8,2%	-76,0%

Analyse des résultats

version 0.9.1opti (Parser opti)

On constate une diminution très importante du temps d’exécution de 43% à 73%. Cette diminution est moins importante pour le fichier russe issu de LaTeX. Cela s'explique par le fait que ce fichier contient presque exclusivement des chaînes \IeC {\cyrr } dont l'analyse nécessite plus de temps.

version 0.10.0 (Text)

On constate une augmentation des temps d’exécution (6% à 22%) et de mémoire avec la version 0.10.0, ou le type String a été remplacé par le type Text et ou le parser n'a pas été optimisé. On note que cette augmentation est plus importante pour le fichier russe issu de LaTeX.

Cette augmentation est surprenante car l'utilisation du module text avait pour vocation d'accélérer le programme et non de le ralentir.

version 0.10.0 (Text + Parser opti)

On constate une diminution des temps d’exécution de 36% à 76% qui est du même ordre que la version 0.9.1opti avec ces quelques nuances:

• Les fichiers venant de LaTeX sont traités un peu plus lentement que la version 0.9.1opti.

• Les fichiers venant de XeTeX sont traités un peu plus rapidement que la version 0.9.1opti.

Interprétation

La diminution de la vitesse d’exécution pour les versions 0.9.1opti et 0.11.0 sont parfaitement explicables à cause de l'optimisation du parser. L'augmentation des temps d’exécution pour la version 0.10.0 et 0.11.0 avec les fichiers issus de LaTeX pourrait s'expliquer par la combinaison parsec plus text. En effet, si on regarde l'implémentation de la bibliothèque parsec, on remarque que la bibliothèque fonctionne nativement avec le type String. Une conversion du type Text vers le type String est donc effectuée ce qui provoque un ralentissement.

Pour en avoir le cœur net, J'ai procédé à une modification de la version 0.11.0 pour forcer le programme à lire les fichiers avec le type String et à les faire analyser avec le type String par parsec. Voyons les résultats de cette version 0.11.1

	0.9.1-O0	0.9.1-O2	0.9.1opti-O0	0.9.1opti-O2	0.10.0-O0	0.10.0-O2	0.11.0-O0	0.11.0-O2
latex fr	2,806	2,005	0,772	0,53	2,783	2,232	0,735	0,541
latex ru	7,295	5,177	4,038	2,938	7,797	6,304	4,135	3,304
xetex fr	2,779	1,961	0,765	0,53	2,793	2,086	0,645	0,477
xetex ru	2,801	1,985	0,762	0,539	2,798	2,148	0,643	0,477

Gain de temps comparé à la version 0.9.1-O2

	0.9.1-O2	0.9.1opti-O2	0.10.0-O2	0.11.0-O2	0.11.1-O2
latex fr	100,0%	-73,6%	11,3%	-73,0%	-75,2%
latex ru	100,0%	-43,2%	21,8%	-36,2%	-44,4%
xetex fr	100,0%	-73,0%	6,4%	-75,7%	-75,4%
xetex ru	100,0%	-72,8%	8,2%	-76,0%	-75,8%

Cette version semble bien avoir amélioré les performances pour les fichiers générés avec LaTeX.

Comparaison avec xindy

J'ai développé HsIndeX afin de palier l'absence de xindy sur ma machine de l'époque. Maintenant que xindy est a nouveau disponible sur ma machine, il serait intéressant de comparer la vitesse d’exécution des deux programmes.

Cette comparaison est à titre informatif car l'implémentation des deux programmes n'est pas identique et HsIndex contient des fonctionnalités absentes de xindy.

time texindy -L french -C utf8 -o testfr.xindy.ind indexes/motsfr.latex.idx

s’exécute correctement en 2,493sec

time texindy -L russian -C utf8 -o testru.xindy.ind indexes/motsru.latex.idx

plante au bout de 16,978sec avec le message d'erreur suivant:

Processing index...
ERROR: CHAR: L'index 0 doit être plus petit que la longueur de la chaîne.

Si on compare ces résultats avec HsIndex, on trouve les gains suivant:

	0.9.1-O2	0.11.1-O2
latex fr	19,4%	80,0%
latex ru	69,5%	83,1%
xetex fr	10,2%	77,9%
xetex ru	39,8%	85,5%

HsIndex est donc beaucoup plus rapide que xindy. Même la version non optimisée 0.9.1

Développer HsIndex n'était donc pas inutile. D'autant plus que les fichiers russes issus de LaTeX semblent causer problème avec xindy.

Conclusion

Ce travail de profiling m'a permis de mettre en évidence les fonctions à améliorer dans mon programme et de quantifier les gains obtenus.

Le parser était donc bien la fonction à optimiser en priorité et non le passage à text dont les gains pour ce programme sont discutables.

Ce travail m'a également montré qu'un parser écrit avec parsec était un peu plus lent si on le faisait travailler avec le type Text.

---

Notes

1.↑	Qui rappelons-le, est une liste de Char.